A large amount of time is required for retrieving, summarizing and sorting or for joining and updating a large amount of data such as a database. In order to solve this, the present inventor proposes a method for retrieving, summarizing and sorting data in a table format extremely fast and a method for joining and updating or for performing transaction processing on data in a table format (JP-A-10-227278 and JP-A-10-338133: PCT/JP99/04300, JP-A-11-151156: PCT/JP00/03465, and JP-A-11-215450: PCT/JP00/05135).
Innovatively, according to a series of these proposed methods, uniform processing can be performed by using no indices. In addition, processing can be performed on a subset by keeping the efficiency.
In order to achieve the fast retrieving, summarizing, sorting, joining and updating, data in a given table format must be converted to data in a predetermined format (this processing will be called “compiling” or “compile processing” hereinafter). In this form, as shown in FIG. 2, a value list and an array (pointer array) are provided. In the value list, item values of a given item are located without any redundancy in a predetermined order. The array includes elements corresponding to record numbers. Each of the elements designates a position in the value list including item values corresponding to the record numbers. A data group of a given item in a predetermined format is referred to as an information block.
The compile processing is required in following cases:    (1) where data in a newly given table format should be converted and be stored into data in a predetermined format;    (2) where a new item is calculated from one or multiple items; and    (3) where data in one table format should be added to data in the other table format, for example, where a table for February is added to a table for January.
In order to implement the compile processing in these cases, item values in a value list may be arranged in a different order by using a known sorting method (for example, quick sorting) conventionally.
However, when an information block is created by using the known sorting method, problems may occur as follows:    (1) In general, O (n*log(n)) comparison computing is required, which needs a large amount of processing time;    (2) When quick sorting is used especially, the processing efficiency may be reduced extremely in some data distributions; and    (3) Fast sorting is difficult by using multiple processors.
It is an object of the present invention to provide a data compiling method, which allows faster processing time and which may not extremely reduce a processing efficiency in some data distributions.
The invention may be also effectively applied to a single processor. Especially, it is another object of the present invention to provide a data compiling method, which can dramatically improve performance in a massive parallel system.